Advances in computing and networking technology have led to the development of new and increasingly complex communications networks. In network communications systems, data is typically transmitted in packages called packets or frames, which may be routed over a variety of intermediate network nodes before reaching their destination. These intermediate nodes (e.g., controllers, base stations, routers, switches, and the like) are often complex computer systems in their own right, and may include a variety of specialized hardware and software components.
Often, multiple network elements will share a single resource. For example, multiple servers may attempt to send data over a single channel. In such situations, resource allocation, coordination, and management are important to ensure the smooth, efficient, and reliable operation of the system, and to protect against sabotage by malicious users.
In the transmission of data over communications networks, network elements typically receive and buffer data packets prior to retransmitting them to their appropriate destinations over data links. For example, each network element may allocate network resources to schedule the retransmission of the data packets. The scheduling may be used in systems to provide differentiated services such as different levels of Quality of Service (QoS). For example, certain important or time critical communications, such as voice or video communications, may be intolerant to delays or are otherwise time critical whereas other less important or less time critical types of communications, such as batch file transfers and emails, may be more tolerant of communication delays. In addition, certain network users may desire (and pay for) higher levels of network availability.
As computer networks evolve and as network traffic increases, providing more bandwidth, lower latency, decreased costs and increased flexibility is becoming increasingly important. Maintaining efficient flow of information over data communication networks is thus becoming increasingly important.
Scheduling algorithms are often employed to ensure that higher priority packets reach their destinations faster than lower priority packets. In particular, scheduling algorithms such as weighted fair queuing (WFQ), also referred to as packetized general processor sharing (PGPS), are often used to select the best packet from among groups of packets in queues contending for bandwidth to facilitate fair bandwidth sharing. Hierarchical scheduling is one method to schedule packets so that the link capacity of the intermediate hops within the hierarchy is not exceeded. At each level of the hierarchy, a selection of the best packet to move forward is made based on a selection criterion such as departure time and/or other numeric metric.